package com.yequan.leetcode.dp.longestCommonSubsequence_1143;

/**
 * @author : Administrator
 * @date : 2020/4/19
 */
public class RecodeLongestCommonSubsequence {

    /**
     * 使用二维数组 int[][] dp 存储text1在text2(或者相反)的最长公共子串长度
     * 这里分两种情况考虑:
     * 1.如果text1和text2(包括其子串中)的最后一个字符相同
     * dp[i][j] = dp[i-1][j-1] + 1;
     * 2.如果不相同
     * dp[i][j] = Max(dp[i-1][j],dp[i][j-1]);
     *
     * @param text1
     * @param text2
     * @return
     */
    public int longestCommonSubsequence(String text1, String text2) {
        int l1 = text1.length();
        int l2 = text2.length();
        int[][] dp = new int[l1 + 1][l2 + 1];
        for (int i = 1; i <= l1; i++) {
            for (int j = 1; j <= l2; j++) {
                dp[i][j] = (text1.charAt(i - 1) == text2.charAt(j - 1))
                        ? dp[i - 1][j - 1] + 1
                        : Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[l1][l2];
    }

}
